/*
 * p1011.cpp
 *
 *  Created on: 2013-5-20
 *      Author: zy
 */

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int dp[110][110], bug[110], value[110];
vector<int> son[110];
int n, m;
int ans;
void dfs(int s, int pa)
{

	for (int i = bug[s]; i <= m; i++)
		dp[s][i] = value[s];
	for (int i = 0; i < son[s].size(); i++)
	{
		int v = son[s][i];
		if (v == pa)
			continue;
		dfs(v, s);
		for (int j = m; j >= bug[s]; j--)
			for (int k = 1; k <= j - bug[s]; k++)
				dp[s][j] = max(dp[s][j], dp[s][j - k] + dp[v][k]);

	}
}
int main()
{
	while (scanf("%d%d", &n, &m), n != -1 || m != -1)
	{

		for (int i = 0; i <= n; i++)
			son[i].clear();
		for (int i = 1; i <= n; i++)
		{
			scanf("%d%d", &bug[i], &value[i]);
			bug[i]=(bug[i]+19)/20;
		}
		for (int i = 1; i < n; i++)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			son[a].push_back(b);
			son[b].push_back(a);
		}
		son[1].push_back(0);
		memset(dp, 0, sizeof(dp));
		if(m==0) {printf("0\n");continue;}
		dfs(1, 0);
		cout << dp[1][m] << endl;
	}
	return 0;
}
